
<!-- saved from url=(0050)http://www.courses.ncsu.edu/csc501/lec/001/hw/hw5/ -->
<HTML><HEAD><META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<TITLE>Homework 5</TITLE>
<STYLE>
<!--
	body{
		padding: 10px;
	}

	td{
		background: #fff;
	}

	.header{
		 background: #eee;
		 font-weight: bold;
	}

	.problem{
		margin-top: 50px;
	}
-->
</STYLE>
</HEAD><BODY>
<H3>Homework 5</H3>
<P>
Deadline: see web page Assignments: Please use the machine osXX.csc.ncsu.edu (Linux) XX=40-55. All programs have to be written in C, translated with gcc and turned in with a corresponding Makefile. Problems 4 is to be solved in the groups of 3 students, problems 1, 2 and 3 are to be solved individually.
</P>
<P>
You may find code on the web that solves parts of these exercises. Feel free to browse this code, read it, learn from it. However, do not copy any code to solve this assignment.
</P>

<OL>
<!--p1 start-->
<LI> (10 points)
Consider the log(N) distributed mutual exclusion algorithm of (<A href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39.5594&rep=rep1&type=pdf">Naimi, Trehel</A>), indicate the state of the processes (numbered 1 to 5), in terms of the 'father' and 'next' variables, that would result from the following sequence of actions: 4R, 4G, 3R, 1R, 5R, 4L, 3G, 3L, 3R, 1G, 2R, 1L, 5G, 5L, 3G.  Also indicate the total number of messages exchanged. Assume that the initial state is such that process 1 has the token and is the father of the other processes.<BR>
<B>Note:</B><BR>
In the action sequence given, the numbers indicate the process ID and<BR>
R - Request token;<BR>
G - Obtain token;<BR>
L - Release token.<BR>
<P></P>
<P>
Turn in problem1.txt.
</P>
</LI>
<!--p1 end-->

<!--p2 start-->
<LI> (10 points) Answer the following questions:
<OL type="a">
<LI>What data structures are used in Chord? Briefly explain their functions. </LI>
<LI>Describe a situation in which Chord may fail to locate the node that stores a particular data item.</LI>
</OL>
<P>
Turn in file problem2.txt
</P>
</LI>
<!--p2 end-->

<!--p3 start-->
<LI>
<P> (25 points)
Design a parallel program for the nVidia CUDA programming environment to find the maximum, minimum, and mean value of an array of numbers. In your implementation, your host code can call as many kernel functions as necessary, but you can only use the kernel functions to find/calculate the required values. 
</P><UL>
<LI>
<B>Input:</B>
The array is initially stored in a data file whose name is the first and only argument of your program. The first line of the data file indicates the length of the array. The array starts from the second line, one number per line. You may assume there are at least 8 numbers and at most 262144=512*512 numbers, but please note that the length of the array is not always power of 2. (Two sample input files are provided below) 
</LI>
<LI>
<B>Output:</B>
Your program should print out the maximum, minimum and mean value of the array. In addition, your program should also print out the execution time for the following procedures of your program:<BR>
1. Memory transfer from host to device<BR>
2. Total computation to find maximum, minimum and <S>median</S> mean value (Start after the data is really in the right memory location, and stop when the result is ready)<BR>
3. Memory transfer from device to host<BR>
4. Overall execution: include input file loading and exclude printing out result.<BR>
</LI>
</UL>
<P></P>
<P>
The following files are provided to solve this exercise: 
</P><UL>
<LI>
<A href="http://www.courses.ncsu.edu/csc501/lec/001/hw/hw5/Makefile">Makefile</A>
</LI>
<LI>
<A href="http://www.courses.ncsu.edu/csc501/lec/001/hw/hw5/a128.dat">a128.dat</A>, <A href="http://www.courses.ncsu.edu/csc501/lec/001/hw/hw5/a1111.dat">a1111.dat</A> (different input files will be used for grading)
</LI>
</UL>
<P></P>
<P>
The following file has to be turned in:
</P><UL>
<LI>p3.cu</LI>
</UL>
<P></P>
<P>
Getting started with CUDA and references: 
</P><UL>
<LI>
<A href="http://moss.csc.ncsu.edu/~mueller/cluster/nvidia/">User Installation (CUDA 2.3)</A>
</LI>
<LI>
<A href="http://developer.download.nvidia.com/compute/cuda/3_0/toolkit/docs/NVIDIA_CUDA_ProgrammingGuide.pdf">CUDA Programming Guide</A>
</LI>
<LI>
<A href="http://developer.download.nvidia.com/compute/cuda/3_0/toolkit/docs/CudaReferenceManual.pdf">CUDA Reference Manual</A>
</LI>
</UL>
<P></P>
</LI>
<!--p3 end-->

<!-- p4 start -->
<LI> (55 points)
The purpose of this problem is to understand the design of a basic
  Distributed hash
  table. <A href="http://portal.acm.org/citation.cfm?id=383071">Chord</A>
  is a the distributed lookup protocol that provides key-value based
  lookup. In the steady state, each node in Chord maintains
  information of only about O(log N) other nodes and resolves all
  lookups via O(log N) messages to other nodes.
<BR><BR> This implementation will however deviate from Chord in many
respects. The guidelines for the basic DHT is as follows:
<UL>
<LI>
<P>
Each node is represented by program running on localhost in a port
number. E.g., 3 Nodes can be running on localhost:50000,
localhost:61111 and localhost:79999
</P>
</LI>
<LI>
<P>
Each node's hash value is the hash value of the string combination of
nodename and port number. E.g., the node of localhost:50000 will have
hash value of the string localhost50000. Hashing is done using MD5
hashing algorithm. Keys are also hashed using the same algorithm.
</P> 
</LI>
<LI>
<P>
Similar to consistent hashing, key to node assignment will be based on
the hash values of keys and nodes. Key k will be assigned to the first
node whose hash value is equal to or follows the hash value of key in
the hash value space.
</P>
</LI>

<LI>
<P>
The operations that the nodes should support from the client program's
perspective are: PUT, GET, QUERY, END. You may choose to introduce
other commands that would be used between node to node operations.
</P><UL>
<LI>The PUT command is used to store the key,value pair. The format of PUT
command is PUT:key:value. A PUT message to a node may need to be
forwarded.</LI>
<LI>The GET command is used to retrieve the key,value pair by using the
key. The format of GET command is GET:key. A GET message to a node may
need to be forwarded.</LI>
<LI>The QUERY command is used to display all the key, value pairs stored
by a node. A QUERY message to a node will not be forwarded. The format of
QUERY command is the text QUERY.</LI>
<LI>The END command is used to end all the nodes. An END message to a node
will require to be forwarded. The format of the END command is the text
END.</LI>
</UL>
<P></P>
</LI>
<LI>
<P>
</P><P>
Each node will be run using the command</P><PRE>		dhtmain &lt;n&gt;
</PRE>where, n is the total number of nodes. E.g., a 3 node DHT
service would be run as: 
<PRE>dhtmain 3
dhtmain 3
dhtmain 3
</PRE>
<BR>Each node will run on a separate console, which will be used to
display outputs of the client command.
<P></P> A client will be run as:<PRE> client &lt;portnumber&gt; &lt;command&gt;</PRE>where command can be any of the commands mentioned
above. For example, a client issuing PUT command to node localhost:50000
would be issued as: 
<PRE>client 50000 "PUT:key1:value1"
</PRE>
The client program needs to be extended to receive result values and
output them (as seen in the example below).
<P></P>
</LI>
<LI>
<P><B>Each node will only keep information of &#8970;log N&#8971;
  other hosts in a finger table</B>. During startup, hosts will
  initialize the node information. All other port numbers should be a
  random number in the range 1024..65535. You should use a local file
  called "nodelist", created by the first node, where each node appends its
  hostname:portno in a separate line. Once the file reaches n lines
  (where n is the maximal number of nodes), the last node initializes
  its fingers. It then sends a START message to its next neighbor in
  the ring. This message then propagates in the ring and results in
  finger initialization (by reading the entire file but only
  initializing its <B>&#8970;log N&#8971; finger entries!</B>) on
  the other nodes until it reaches the initiator, where is it silently
  absorbed. Only after this point should queries with the above
  commands be issued (using the ports listed in the "nodelist"
  file). The "nodelist" file should be removed when the END message
  is received by one of the nodes (your choice which one).</P>
<P> This assignment will not cover node failures or joining/leaving.
</P>
</LI>
<LI>
<P>
A sample output in the node console for a set of commands is given below.
<BR>
Client commands: 
</P><PRE>	$ ./client 50000 "PUT:key1:value1"
	$ ./client 50000 "PUT:key2:value2"
	$ ./client 50000 "PUT:key3:value3"
	$ ./client 50000 "GET:key1"
          found key1:value1
	$ ./client 50000 "GET:key2"
          found key2:value2
	$ ./client 50000 "PUT:key53:value53"
	$ ./client 50000 "QUERY"
	$ ./client 50000 "END"
</PRE>

Node output:
<PRE>	$ ./dhtmain 3
	DHT node (19f8fa816abe2342dc6621c74a9414b4): Listening on port number 50000 . . . 
	(key:value) =(key1 [c2add694bf942dc77b376592d9c862cd] :value1) inserted
	PUT for key2 [78f825aaa0103319aaa1a30bf4fe3ada] was forwarded to localhost:50002
	PUT for key3 [3631578538a2d6ba5879b31a9a42f290] was forwarded to localhost:50002
	Found key value pair (key1:value1)
	GET for key2 [78f825aaa0103319aaa1a30bf4fe3ada] was forwarded to localhost:50002
	(key:value) =(key53[128a85ec696ff60d0cf5cc1b6e1a4805]:value53) inserted
	Key		Value
	------------------------------
	key1		value1
	key53		value53
	------------------------------
</PRE>

<P></P>
</LI>
</UL>
<P>
The following files contain the basic client server functionality that
you can use to build the DHT nodes.
</P><UL>
<LI><A href="http://www.courses.ncsu.edu/csc501/lec/001/hw/hw5/q3/dhtmain.c">dhtmain.c</A></LI>
<LI><A href="http://www.courses.ncsu.edu/csc501/lec/001/hw/hw5/q3/client.c">client.c</A></LI>
<LI><A href="http://www.courses.ncsu.edu/csc501/lec/001/hw/hw5/q3/Makefile">Makefile</A></LI>
</UL>   
<P></P>
<P>
The following files have to be turned in: 
</P><UL>
<LI>dhtmain.c</LI>
<LI>client.c</LI>
<LI>Makefile</LI>
<LI>README</LI>
</UL>   
 <P></P>
<P></P>
</LI>
<!-- p4 end -->
 <LI>Peer evaluation: Each group members has to submit a
       <A href="http://www.courses.ncsu.edu/csc501/lec/001/hw/peer.txt">peer evaluation form</A>.
</LI>
</OL>
  <P><STRONG>Please read the message board for clarifications and possible
    answers to questions you might have.</STRONG>


</P><H2>Grading, comments, working in groups, turn in assignments etc.</H2>

  <P>See <A href="http://www.courses.ncsu.edu/csc501/lec/001/hw/hw1/">homework 1</A> for details.</P>

  <P class="dataFollows">Make sure you include the author information:</P>
  <PRE>Single Author info:
  username FirstName MiddleInitial LastName
Group info:
  username FirstName MiddleInitial LastName
  username FirstName MiddleInitial LastName
  username FirstName MiddleInitial LastName</PRE>




  

</BODY></HTML>